package 课程设计;

import java.util.ArrayList;
import java.util.List;

public class Road {
    public final static int INFINITY=0;
    void showArray(int arr[][]) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
               // System.out.print(arr[i][j] + " ");
            }
           // System.out.println();
        }
       // System.out.println();
    }

    /**
     * *************************************************************************************************************
     * 能够得到任意两个点之间的最短距离的Floyd算法 可以有负权边，但是不能有负权环
     *
     * @param dist 最初的节点之间的距离矩阵，注意当两个节点之间不能到达是，初始值要设置 大于INF
     * @param path 不想要中间路径的时候，可以直接去掉，中间路径的初始是 :"顶点i"到"顶点j"的最短路径是经过顶点j。
     */
    public void findFloydRoad(int[][] dist, int[][] path) {

        int mVex = dist.length;
        for (int k = 0; k < mVex; k++) {
            for (int i = 0; i < mVex; i++) {
                for (int j = 0; j < mVex; j++) {
                    if (dist[i][j] > (dist[i][k] + dist[k][j])) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[i][k];
                    }
                }
            }
        }

    }

    /**
     * 用于输出弗洛伊德算法的路径
     *
     * @param path  得到的路径矩阵
     * @param start 开始点，注意这个点是从零开始计数的  例如从 0到3
     * @param end   结束点，也是从零开始计数的
     * @return List数组  返回的值也是从零开始计数的。
     */
    public List<Integer> findTheRoad(int[][] path, int start, int end) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(start);
        int temp = path[start][end];
        while (temp != end) {
            list.add(temp);
            temp = path[temp][end];
        }
        list.add(end);
        return list;
    }

}

